All Questions
8 questions
2votes
1answer
131views
Maximum cardinality disjoint cycle cover in undirected graphs
I call a maximum cardinality disjoint cycle cover of a graph a vertex-disjoint cycle cover containing the maximum possible number of cycles in the graph. What is known about the complexity of this ...
- 948
1vote
0answers
81views
What are the fastest known parameterized algorithms for Grid Tiling?
Let $k$ and $n$ denote positive integers. In the $k$-GridTiling problem, for every pair of indices $(i,j)\in \{1, \dots, k\}^2$ we get a subset $S_{ij}\subseteq \{1, \dots, n\}^2$ of pairs of the ...
- 696
9votes
1answer
230views
Is the Triangle Finding decision problem in $coNTIME(\tilde{O}(n^2))$?
The Triangle Finding decision problem asks whether there exists a triangle in a graph $G$ containing $n$ vertices. A triangle is a triple of vertices $(a, b, c)$ such that $a$ is adjacent to $b$, $b$ ...
- 5,177
0votes
1answer
104views
Complexity status of restricted k-clique [closed]
Restricted $k$-clique: Input: $(G,v,k)$ where $v$ is vertex in $V$ Output: k-clique containing vertex $v$. What is the space and time complexity status of this Restricted $k$-clique problem? Is ...
- 185
3votes
1answer
275views
Minimum length walk from s to t covering a subset of vertices
I want to find the current literature for the following problem (I have searched on google/asked friends/some Profs didn't get much useful results yet): Input: weighted undirected graph G = (V,E), $...
- 263
6votes
1answer
410views
Complexity of the directed Steiner tree problem on special graph classes
I am interested in the complexity of the directed Steiner tree problem: Given a weighted digraph $D=(V,E)$, a root $r\in V$ of $D$, and a set of terminals $T\subseteq V$. The objective is to find a ...
- 141
10votes
1answer
716views
Fastest known algorithm for finding simple paths through given set of vertices
For an undirected graph $G$ and a given set $S$ of vertices, what is the asymptotically fastest known algorithm for finding a simple path containing all elements of $S$. What if we require the path to ...
- 103
6votes
0answers
249views
Restricted Reachability Problem
Let $G$ be a directed acyclic graph with $V$ vertices and $E$ edges. Choose some subset of $n\leq V$ "special" vertices $\{v_i\}_{i=1}^n$. How efficiently can we preprocess $(G, \{v_i\})$ so that we ...
- 800
